package summary;

import java.util.PriorityQueue;

/**
 * @Author: 海琳琦
 * @Date: 2022/4/7 12:15
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 */
public class Title215 {

    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> a.compareTo(b));
        for (int i = 0; i < nums.length; i++) {
            priorityQueue.offer(nums[i]);
            while (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return priorityQueue.poll();
    }

    public int findKthLargest1(int[] nums, int k) {
        heapSort(nums, k);
        return nums[nums.length - k];
    }

    private void heapSort(int[] nums, int k) {
        int n = nums.length;
        //建立大根堆
        buildHeap(nums, n);
        while (n > 0 && k-- > 0) {
            swap(nums, 0, --n);
            heapify(nums, 0, n);
        }
    }

    private void buildHeap(int[] nums, int n) {
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(nums, i, n);
        }
    }

    private void heapify(int[] nums, int i, int n) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int maxIndex = i;
        if (left < n && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if (right < n && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        if (maxIndex != i) {
            swap(nums, i, maxIndex);
            heapify(nums, maxIndex, n);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 1, 5, 6, 4};
        findKthLargest(nums, 2);
    }
}
